#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/17 10:47
# ===========================================
#       题目名称： 5. 最长回文子串
#       题目地址： https://leetcode.cn/problems/longest-palindromic-substring/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================


class Solution:
    """
        实现思路：
            通过双指针的形式进行来回遍历 通过反转来找到最大回文子串
    """
    def longestPalindrome(self, s):
        max_s = s[0]  # 定义最大的字符串
        left, right = 0, len(s) - 1  # 定义左右指针
        while left < right:
            if s[left] == s[right] and right - left >= len(max_s):
                temp_s = s[left: right + 1]
                left_s, right_s = temp_s[:int(len(temp_s) / 2)], ""
                if len(temp_s) % 2 == 0:  # 偶数
                    right_s = temp_s[int(len(temp_s) / 2):]
                else:
                    right_s = temp_s[int(len(temp_s) / 2) + 1:]
                right_s = right_s[::-1]  # 反转
                if left_s == right_s and len(max_s) < len(temp_s):
                    max_s = temp_s
            if left == right - 1:
                left += 1
                right = len(s) - 1
            else:
                right -= 1
        return max_s

    def longestPalindrome3(self, s):
        """
            时间超限
        """
        s = list(s)
        left, right = 0, len(s) - 1  # 定义左右指针
        max_stack = [s[0]]
        while left < right:
            temp_s = s[left: right + 1]
            temp_x = temp_s.copy()
            temp_y = temp_s.copy()
            temp_y.reverse()
            if temp_x == temp_y and len(max_stack) < len(temp_s):
                max_stack = temp_s
            if right - 1 == left:
                if left + 1 >= len(s) - 1:
                    break
                else:
                    left += 1
                    right = len(s) - 1
            else:
                right -= 1
        return "".join(max_stack)

    def longestPalindrome2(self, s):
        """
            超时
        """
        max_stack = []
        s = list(s)
        for i in range(len(s)):
            for j in reversed(range(i, len(s))):
                stack = s[i: j + 1]
                is_find = True
                while stack and len(stack) > 1:
                    first = stack.pop(0)
                    last = stack.pop()
                    if first != last:
                        stack.clear()
                        is_find = False
                        break
                if is_find and len(s[i: j + 1]) > len(max_stack):
                    max_stack = s[i: j + 1]

        return "".join(max_stack)


if __name__ == '__main__':
    s = Solution()
    # bab
    print(s.longestPalindrome(s="babad"))
    # bb
    print(s.longestPalindrome(s="cbbd"))
    # a
    print(s.longestPalindrome(s="a"))
    # a
    print(s.longestPalindrome(s="ac"))
    # ccc
    print(s.longestPalindrome(s="ccc"))
